1. Field of the Invention
This invention is directed to computer circuits, in general, and to error detection and correction circuits using 5 parity trees, in particular.
2. Prior Art
The reliability of solid-state electronic circuits has greatly improved during the past decade. Despite this improvement, however, digital system designers are still concerned with system reliability during the hardware design phase. The designer has a number of design options that will improve the reliability and maintainability of the fundamental system. One such option is to duplicate the entire system. The cost of this approach is virtually prohibitive and is used only in designs where the highest degree of reliability is required. A more common approach is to add only enough extra (non-essential) hardware to allow detection of the most common types of system errors. For example, the hardware necessary to add a single extra bit to the system word is often provided. This extra bit, called the "parity bit", allows the detection of an error that affects only a single bit (or an odd number of bits) of the system word. The error could be caused by hardware failure, noise on the transmission line, or the like. The information to be placed into this parity bit is chosen so that the "parity word", consisting of the original system word plus the parity bit, contains an odd number of "1's" (odd parity) or an even number of "1's" (even parity).
The function of a parity generator is to examine the system word and calculate the information required for this added parity bit. Once the parity bit has been included, the "parity word" can be examined after any transmission to determine if a failure or error has occurred.
A parity detection circuit (parity checker) examines the parity word to see if the desired odd or even parity still exists. If an error has occurred, the system control can be informed that the system has not functioned properly.
The fundamental operation required in parity generation and detection circuits, viz. that of comparing inputs to determine the presence of an odd or even number of "1.+-.", can be effectively performed by Exclusive-OR logic circuits. A basic Exclusive-OR circuit performing the function AB+AB serves to calculate parity over inputs A and B. Exclusive-OR gates, and also Exclusive-NOR gates, can be interconnected to form parity trees and, therefore, perform parity calculations over longer word lengths. Integrated circuits consisting of Exclusive-OR or Exclusive-NOR gates interconnected to form parity trees are available in the art.
A simple parity scheme detects the presence of a single error in a word. If two errors occur, the output does not indicate that an error has occurred. Thus, the above parity scheme will detect an odd number of errors but fail if an even number of errors occurs.
Schemes have been devised that allow the detection and correction of a single error. Such procedures not only have to recognize that an error has occurred, but also detect which bit is in error. Several extra bits must be added to the system word to accomplish this single-error correction. One such scheme is referred to as Hamming parity single-error detection and correction. A single-error Hamming parity code generator examines the message bits and generates the required parity bits. The generated parity bits are inserted into the message bits in a prescribed manner. This longer "parity word", containing both the original parity bits and the message bits, can now be transmitted or processed. The accuracy of this parity word can be examined later by a single-error Hamming parity detection circuit. The output of the detection circuit indicates the binary position in the parity word of the bit in error provided only a single error has occurred.